The present invention relates generally to transformation of a digital description of a color of a picture element (pixel) from one color space to another, and, in particular, to accomplishing this transformation as rapidly as possible during real-time image editing on a digital computer.
Transformation of pixels from one color space to another color space is a well-understood problem in the prior art. The problem is especially acute in graphical image editing when a user attempts to match colors displayed on a computer monitor (one color space) to colors of printed objects (another color space). One difficulty is that often the two color spaces do not map easily between each other, such as for example in the scenario described above.
Colors displayed on a computer monitor are typically additive colors (i.e., orthogonal colors such as red, green and blue) that are added together to create white. Printing historically uses offset-printing techniques and has been performed using subtractive colors (i.e., orthogonal colors such as cyan, magenta, yellow and black) that are subtracted away to create white (the color of the underlying medium).
Since the graphical image editing scenario is a common one, the problem of matching colors in the cyan, magenta, yellow and black (CMYK) color space to colors in the red, green and blue (RGB) color space is typical of image editing systems and software. This problem occurs in other color spaces as well, such as CIE-XYZ, CIE-LUV, or CIE-LAB, or PhotoYcc, for example.
Colors in the offset-printing processes are commonly produced by printing four different layers or separations in one of each of the cyan, magenta, yellow and black inks. Within each layer, dots (halftone dots) of different sizes are printed over a regular grid of possible halftone dot locations. A computer description of the color of any one pixel includes a quadruplet of values, one for each of the four CMYK inks.
Typically, each color value lies within a range of 0 to 255, represented in the computer as an eight-bit byte. The magnitude of the value indicates the size (spatial area) of the halftone dot. When the magnitude is zero the dot has no size and is not drawn. When the magnitude is 255, the dot has maximum size and it fills its grid cell. Thus a CMYK quadruplet value of (c,m,y,k)=(0,0,0,0) indicates that there is no ink on the paper and so the color is the white of the paper. Conversely, a CMYK quadruplet value of (c,m,y,k)=(255,255,255,255) indicates maximum ink on the paper and the color of the pixel is black.
The color of images displayed on cathode ray tubes (CRTs) used as video display monitors are commonly produced by passing an electron beam across arrays of triplets of phosphor dots, with each pixel represented by one set of the dot triplets. A phosphor dot, when stimulated, produces a red, green or blue light (RGB light). There is one of each of these three different types of phosphor dots in each of the triplets making up a pixel.
A computer description of the color of any one pixel includes a triplet of values, one for each of the three RGB phosphors. Often each color value lies within a range 0 to 255, again represented as an eight-bit byte. The magnitude of the color value indicates the amount of illumination being produced by the phosphor of the given color. When the magnitude is zero, the corresponding phosphor produces no illumination. When the magnitude is 255, the phosphor produces maximum illumination. Thus, an RGB triplet value of (r,g,b)=(0,0,0) indicates that the pixel at the appropriate position on the screen is black, and an RGB triplet value of (r,g,b)=(255,255,255) indicates that the pixel at the appropriate position on the screen is white.
Reflected light produces the color of CMYK pixels on a printed page. Projected light produces the color of RGB pixels on a CLOT. The underlying physics associated with these different mechanisms for producing color are profoundly different. The former (CMYK colors) are subtractive colors and the latter (RGB colors) are additive colors. The problem succinctly stated is thus: a practitioner of the graphics arts must be able to see an image on a CRT displayed using an additive RGB color representation that is as close as is possible to the subtractive CMYK color representation of that same image. A similar problem occurs when the practitioner has acquired an additive RGB representation of a scene from a color scanner, and needs to print a subtractive CMYK representation that is as close to the scanned original as possible.
In the construction of hardware and software applications for the graphic arts, it is important to be able to translate between additive RGB representations and subtractive CMYK representations while maintaining color fidelity.
Color scientists have proposed algorithms which will effect the transformation from subtractive CMYK color to additive RGB colors and vice-versa. A pioneering work related to transforming colors between these color spaces was produced by Neugebauer ("Die theoretischen Grundlagen des Mehrfarbenbuchdrucks"), hereby expressly incorporated by reference for all purposes. Neugebauer's original algorithms have been extended and refined by Yule and Neilsen ("The Penetration of Light into Paper and its Effect on Halftone Reproduction") and by Viggiano ("Modeling the Color of Multi-Colored Halftones"), both hereby expressly incorporated by reference for all purposes.
When converting from CMYK color to RGB color (or vice-versa) on a digital computer, the Neugebauer algorithm is time consuming, often so time consuming as to be unusable in a software application that makes the color transformations in real-time. The algorithms produced by the enhancements of Viggiano, and Yule and Neilsen are even more time consuming than Neugebauer's original algorithm. Therefore, real commercial systems and applications that transform between CMYK and RGB colors cannot use the computationally-intensive (and time consuming) algorithms for mapping colors from one color space to the other, if the mapping is to occur in real-time.
The prior art developed a table lookup process to enhance the speed of transformation between the color spaces relative to use of the algorithmic transformations. There are three stages in the evolution of table lookup as it exists in the prior art. If these table lookup methods are thought of as successors to the algorithmic methods, we have a four-stage history of color conversion:
(0) Algorithmic Color Conversion (as described above) PA1 (1) Full-Table Lookup PA1 (2) Sampled-Table Lookup PA1 (3) Sampled-Table Lookup plus Algorithmic Interpolation. PA1 Step 1: Table Lookup, to get the Base Values, R0, G0, B0. PA1 Step 2: Algorithmic Computation, to calculate the delta values, RD, GD, BD.
Stages 1-3 identify table lookup techniques spanning a virtual evolution (see, for example, U.S. Pat. No. 5,241,373) towards improved color transformation performance. This evolution is virtual because few, if any actual implementations in the prior art, use the technology at stages (1) and (2). Rather, presentation of this evolution explains the need for the stage (3) technology that is actually used. Thinking of stages (1)-(3) as successors to the algorithmic methods provides the four-stage history of color conversion presented above.
The following examples all assume transformation from CMYK to RGB space, but the examples could be presented equally as well for translation from RGB to CMYK space, or for translations between other color spaces.
The idea behind color transformation by table lookup provides for constructing a table that is indexed by the C, M, Y and K values of a pixel. Any cell indexed by these CMYK values contains the RGB triplet corresponding to the particular index values identifying the cell. Use of table lookup to do color transformation requires a priori population of the table with transformed colors. Populating the table requires that for each quadruplet corresponding to a valid (C,M,Y,K) input, the corresponding (R,G,B) triplet is determined and then placed in the appropriate cell in the table.
The speed savings results from the observation that the process of populating the cells in the table can be done off-line (i.e., done separately, at a different place and time than that at which the application actually uses the table). Therefore, it is no longer necessary to calculate in real-time the (CMYK) to (RGB) equivalencies by algorithmic means. In fact, complex and time-consuming experimental methods can be optionally used instead. Note that the actual values in the table or the method selected to choose the values play no role in the operation of the table lookup method.
For implementations using a full-table lookup method (evolution stage 1), there is one cell in the table for every discernible input color. In the case of CMYK input color as described above, with each component (C, M, Y, or K) represented by a an eight-bit byte, the byte is typically represented as an unsigned binary number. One preferred transformation method (in terms of accuracy) includes a lookup table indexed by the four C, M, Y and K values to access a particular cell to produce an associated R value. Such a table has thirty-two (8 bits/input * 4 inputs) bits of input. Therefor, such a table has 232 cells. Each such cell stores a one byte value representing the value of the transformed color, such as the R value. A full lookup table for transforming CMYK values to an R value would, therefore, occupy four billion bytes. To transform the CMYK values to the other components, i.e., the G and B components, requires similarly sized tables. Thus, a full table lookup for accurately transforming a particular CMYK value to a corresponding RGB value requires a total of twelve billion bytes.
A table of such size is much too large to be stored and manipulated effectively by current desktop computer systems. There is potentially great costs associated with populating such a table. Since full-table lookup methods produce exorbitantly large tables, a method using smaller tables is desirable.
One way to reduce the number of entries in a table is to use a sampled table. A sampled table does not have a cell for each possible (CMYK) input quadruplet, but has a cell for only a sample (a subset) of these inputs. For example, in the case of the example identified above when there are 256 possible values for each of C, M, Y and K, such a table can be sampled, by building a new table that contains entries for a reduced number of indices along each of the tables' axes (C, M, Y, and K), with a corresponding reduction in the number of cells and the size of the table.
A simple way to reduce the number of indices is to decrease their number by a factor which is a power of 2. Reducing the number of indices in this fashion is done, in turn, by retaining only those indices that, when reexpressed as binary numbers, have their least-significant n bits (n&gt;0 and n&lt;8) set equal to zero. The numbers, n, of bits set to zero can differ for the four axes (the four color indices), and can be denoted by nC, nM, nY and nK. For example, a particular application may set nC=nM=nY=4, and set nK=3. This would provide for more accurate transformations of black, a color that the human eye is especially sensitive to.
Only using selected ones of the most-significant bits of CMYK color values means that along the cyan, magenta and yellow axes, the table would use only those numbers having a binary expression of the form XXXX0000. Specifically, these numbers are 0, 16, 32, 48, . . . , 240. As a consequence, there will be only 16 possible cyan index values (and similarly 16 magenta index values and 16 black index values). Since nK was set equal to 3 in this example, along the black axis the sampled table will retain only those numbers whose binary expression is of the form XXXXX000. These are, specifically, the numbers 0, 8, 16, 24, 32, . . . , 248. For black then, there will be 32 possible black index values.
The number of bits required to express each component is four for C, M, and Y, and is five for K. This means that the sampled table example uses a total of 17 (3*4+5) bits for indexing, or a total of 131072 cell entries. For transforming the CMYK to RGB, each CMYK value has a corresponding R value, a corresponding G value and a corresponding B value. Thus, the size of the sampled lookup table must be 131072*3, or 393210 bytes. As compared to the full table lookup, the size of the sampled lookup table is now much more manageable (393210 versus four billion bytes) for each color component.
In operation, there is a simple, but inelegant, way to implement a sampled lookup table to convert (CMYK) to (RGB) values. Whenever a given (CMYK) quadruplet is input, its components, C, M, Y, and K are reexpressed as binary numbers. The least-significant nC, nM, nY and nK bits of each eight bit byte are set to zero, thus yielding a new quadruplet (C0, M0, Y0, K0). This truncated quadruplet is then used as the index into the sampled table, and a corresponding (RGB) triplet is looked up. The system associates this (RGB) triplet with the ORIGINAL, untruncated, (CMYK) quadruplet.
The method described above for implementing the sampled lookup table is inelegant because it produces a number of errors, including what K. Douglas Gennetten in his article, "RGB to CMYK conversion using 3-D barycentric interpolation" (hereby expressly incorporated by reference for all purposes) calls Type 2 errors. Type 2 errors are "systematically arranged step errors. This type of error is unique to digital imaging and is distinguishable by its characteristic false contouring--an effect similar to posterization in the graphic arts. A common cause of Type 2 error in inexpensive PC-based systems is an inadequate number of gray levels somewhere within the image path."
In other words, since the least-significant bits of the CMYK values are not used, one RGB value represents several different CMYK values (i.e., several different CMYK values all map to the same RGB value). If the image being converted includes a color gradient gradually ranging over a large enough CMYK spectrum, bands of color appear in the converted image rather than the desired gradient.
Thus, the stage 1 evolution is impractical because it is too memory intensive and the stage 2 evolution has better memory requirements but it provides unacceptable accuracy. The stage 3 evolution is a compromise between the high quality color conversion, as is possible under evolution stage 1 and the memory savings of stage 2, that adds an interpolation process to the stage 2 sampled table lookup.
One example of a stage 3 design is described further. Let (C,M,Y,K) be an original CMYK input quadruplet, and (R,G,B) be the RGB triplet that results from the sampled table lookup plus interpolation method. Let (C0, M0, Y0, K0) be the truncated (C,M,Y,K) as described above. In other words, C0 is the value of C after its least-significant nC bits have bit set equal to zero. C0 is the largest cyan value that (a) is smaller than or equal to C, and (b) is an index in the Sampled Lookup Table. Let (C1, M1, Y1, K1) be, respectively, the smallest CMYK values that are larger than (C0, M0, Y0, K0), respectively, but that are also indices in the sampled lookup table.
For example, when C=33, then C0=32 (the largest number &lt;=C that is an index to the sampled table) and C1=48 (the next index after C0 in the table). Let (R0, G0, B0) represent the RGB triplet stored in the sampled lookup table at the cell corresponding to the index (C0, M0, Y0, K0). In general, whenever (Ci, Mi, Yi, Ki) is an input quadruplet for the sampled table, let f(Ci, Mi, Yi, Ki) denote the RGB triplet stored in cell (Ci, Mi, Yi, Ki) of the sampled table. Notice that, given the latter notational convention we can express (R0, G0, B0) as (R0, G0, B0)=f(C0, M0, Y0, K0).
The preceding notational system allows description of the parallelepiped (really hyper-parallelepiped, because it is four dimensional) containing the point (CMYK). This hyper-parallelepiped has sixteen vertices:
(C0,M0,Y0,K0), (C1,M0,Y0,K0), (C0,M1,Y0,K0), (C0,M0,Y1,K0), (C0,M0,Y0,K1), (C1,M1,Y0,K0), (C1,M0,Y1,K0), (C1,M0,Y0,K1), (C0,M1,Y1,K0), (C0,M1,Y0,K1), (C0,M0,Y1,K1), (C0,M1,Y1,K1), (C1,M0,Y1,K1), (C1,M1,Y0,K1), (C1,M1,Y1,K0), (C1,M1,Y1,K1).
The sampled table contains RGB triplets, f(C0,M0,Y0,K0), at all sixteen of these vertices. Under most lookup-plus-interpolation schemes:
(R,G,B)=(R0, G0, B0)+(RD, GD, BD)
where
(RD, GD, BD)=some algorithmically calculated function of (C,M,Y,K) and of the RGB triplets at the sixteen vertex points; i.e., the sixteen RGB triplets f(C0,M0,Y0,K0), f(C1,M0,Y0,K0), f(C0,M1,Y0,K0), f(C0,M0,Y1,K0), f(C0,M0,Y0,K1), f(C1,M1,Y0,K0), f(C1,M0,Y1,K0), f(C1,M0,Y0,K1), f(C0,M1,Y1,K0), f(C0,M1,Y0,K1), f(C0,M0,Y1,K1), f(C0,M1,Y1,K1), f(C1,M0,Y1,K1), f(C1,M1,Y0,K1), f(C1,M1,Y1,K0), f(C1,M1,Y1,K1). The `D` in (RD, GD, BD) denotes `Delta`, in the sense that these three values are deltas from the (R0, G0, B0) values to the actual (R, G, B) values.
It is appropriate to call such a scheme an interpolation scheme because the sixteen vertices are the vertices of the hyper-parallelepiped segment of the base lookup table which envelops the actual (C,M,Y,K) input value, therefore the desired value is within the region of the hyper-parallelepiped. In actual implementations, the value of (RD,GD,BD) is influenced by the values of each vertex to the extent that the point is near that vertex.
Various specific interpolation algorithms exist in the prior art. James M. Kasson et al. in their article "A tetrahedral interpolation technique for color space conversion," describe six classes of interpolation, which they characterize as (1) Tetrahedral Interpolation, (2) Trilinear (or Multilinear) interpolation, (3) Kanamori interpolation, (4) Clark interpolation, and (5) Diphenoid interpolation. Tetrahedral interpolation is described by T. Sakamoto in his U.S. Pat. No. 4,275,413. Kanamori interpolation is described by Kanamori and Kotera in their article "Color Correction Technique for Hard Copies by 4-Neighbors Interpolation Method," cited above. Clark interpolation is described by Clark et al. in U.S. Pat. No. 4,477,833. These references are all expressly incorporated by reference for all purposes.
A common drawback to all these conventional lookup-plus-interpolation methods is that they add an algorithmic component to the lookup component, and can be subject to speed penalties similar to the original purely algorithmic methods such as those of Neugebauer and Viggiano, described above. Some systems can provide for specialized hardware to improve the speed performance of algorithmic calculations. Requiring specialized hardware limits the number of systems such a process could be applicable to.
To summarize, in a system using conventional lookup-plus-interpolation, two steps are carried out:
Step 2 can be slow, and hence can negate many of the original benefits obtained by using table lookup methods instead of algorithmic methods.
Kanamori, Kawakami and Kotera recognized that the algorithmic computation in step 2 could be slow. U.S. Pat. No. 5,241,373 described techniques for making algorithmic interpolation faster. However, these techniques still do algorithmic interpolation as they still perform multiplicative operations in order to calculate the delta values RD, GD and BD. The speed at which the final result is determined is improved.